<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">

<html xmlns="http://www.w3.org/1999/xhtml">
 <meta>
  <!-- Stylesheets -->
  <link href="../web.css" type="text/css" rel="stylesheet"></link>
  <link href="../pygmentize.css" type="text/css" rel="stylesheet"></link>
  <title>VLFeat - Documentation - C API</title>
  <link rel="stylesheet" type="text/css" href="../doxygen.css"></style>

  <!-- Scripts-->
  
 </meta>

 <!-- Body Start -->
 <body>
  <div id="header">
   <!-- Google CSE Search Box Begins -->
   <form action="http://www.vlfeat.org/search.html" method="get" id="cse-search-box" enctype="application/x-www-form-urlencoded">
    <div>
     <input type="hidden" name="cx" value="003215582122030917471:oq23albfeam"></input>
     <input type="hidden" name="cof" value="FORID:11"></input>
     <input type="hidden" name="ie" value="UTF-8"></input>
     <input type="text" name="q" size="31"></input>
     <input type="submit" name="sa" value="Search"></input>
    </div>
   </form>
   <script src="http://www.google.com/coop/cse/brand?form=cse-search-box&amp;lang=en" xml:space="preserve" type="text/javascript"></script>
   <!-- Google CSE Search Box Ends -->
   <h1><a shape="rect" href="../index.html" class="plain"><span id="vlfeat">VLFeat</span><span id="dotorg">.org</span></a></h1>
  </div>
  <div id="headbanner">
   Documentation - C API
  </div>
  <div id="pagebody">
   <div id="sidebar"> <!-- Navigation Start -->
    <ul>
<li><a href="../index.html">Home</a>
</li>
<li><a href="../download.html">Download</a>
</li>
<li><a href="../doc.html">Documentation</a>
<ul>
<li><a href="../mdoc/mdoc.html">Matlab API</a>
</li>
<li><a href="index.html" class='active' >C API</a>
</li>
<li><a href="../man/man.html">Man pages</a>
</li>
</ul></li>
<li><a href="../overview/tut.html">Tutorials</a>
</li>
<li><a href="../applications/apps.html">Applications</a>
</li>
</ul>

   </div> <!-- sidebar -->
   <div id="content">
    
    <link rel="stylesheet" type="text/css" href="../doxygen.css"></style>
    <div class="doxygen">
<div>
<!-- Generated by Doxygen 1.7.5.1 -->
  <div id="navrow1" class="tabs">
    <ul class="tablist">
      <li><a href="index.html"><span>Main&#160;Page</span></a></li>
      <li class="current"><a href="pages.html"><span>Related&#160;Pages</span></a></li>
      <li><a href="annotated.html"><span>Data&#160;Structures</span></a></li>
      <li><a href="files.html"><span>Files</span></a></li>
    </ul>
  </div>
</div>
<div class="header">
  <div class="headertitle">
<div class="title">Agglomerative Information Bottleneck (AIB) </div>  </div>
</div>
<div class="contents">
<div class="textblock"><dl class="author"><dt><b>Author:</b></dt><dd>Brian Fulkerson </dd>
<dd>
Andrea Vedaldi</dd></dl>
<p><a class="el" href="aib_8h.html">aib.h</a> implemens the Agglomerative Information Bottleneck (AIB) algorithm as first described in <a class="el" href="citelist.html#CITEREF_slonim99agglomerative">[11]</a> .</p>
<p>AIB takes a discrete valued feature <img class="formulaInl" alt="$x$" src="form_0.png"/> and a label <img class="formulaInl" alt="$c$" src="form_1.png"/> and gradually compresses <img class="formulaInl" alt="$x$" src="form_0.png"/> by iteratively merging values which minimize the loss in mutual information <img class="formulaInl" alt="$I(x,c)$" src="form_2.png"/>.</p>
<p>While the algorithm is equivalent to the one described in <a class="el" href="citelist.html#CITEREF_slonim99agglomerative">[11]</a> , it has some speedups that enable handling much larger datasets. Let <em>N</em> be the number of feature values and <em>C</em> the number of labels. The algorithm of <a class="el" href="citelist.html#CITEREF_slonim99agglomerative">[11]</a> is <img class="formulaInl" alt="$O(N^2)$" src="form_3.png"/> in space and <img class="formulaInl" alt="$O(C N^3)$" src="form_4.png"/> in time. This algorithm is <img class="formulaInl" alt="$O(N)$" src="form_5.png"/> space and <img class="formulaInl" alt="$O(C N^2)$" src="form_6.png"/> time in common cases ( <img class="formulaInl" alt="$O(C N^3)$" src="form_4.png"/> in the worst case).</p>
<h2><a class="anchor" id="aib-overview"></a>
Overview</h2>
<p>Given a discrete feature <img class="formulaInl" alt="$x \in \mathcal{X} = \{x_1,\dots,x_N\}$" src="form_7.png"/> and a category label <img class="formulaInl" alt="$c = 1,\dots,C$" src="form_8.png"/> with joint probability <img class="formulaInl" alt="$p(x,c)$" src="form_9.png"/>, AIB computes a compressed feature <img class="formulaInl" alt="$[x]_{ij}$" src="form_10.png"/> by merging two values <img class="formulaInl" alt="$x_i$" src="form_11.png"/> and <img class="formulaInl" alt="$x_j$" src="form_12.png"/>. Among all the pairs <img class="formulaInl" alt="$ij$" src="form_13.png"/>, AIB chooses the one that yields the smallest loss in the mutual information</p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\[ D_{ij} = I(x,c) - I([x]_{ij},c) = \sum_c p(x_i) \log \frac{p(x_i,c)}{p(x_i)p(c)} + \sum_c p(x_i) \log \frac{p(x_i,c)}{p(x_i)p(c)} - \sum_c (p(x_i)+p(x_j)) \log \frac {p(x_i,c)+p(x_i,c)}{(p(x_i)+p(x_j))p(c)} \]" src="form_14.png"/>
</p>
<p>AIB iterates this procedure until the desired level of compression is achieved.</p>
<h2><a class="anchor" id="aib-algorithm"></a>
Algorithm details</h2>
<p>Computing <img class="formulaInl" alt="$D_{ij}$" src="form_15.png"/> requires <img class="formulaInl" alt="$O(C)$" src="form_16.png"/> operations. For example, in standard AIB we need to calculate</p>
<p class="formulaDsp">
<img class="formulaDsp" alt="\[ D_{ij} = I(x,c) - I([x]_{ij},c) = \sum_c p(x_i) \log \frac{p(x_i,c)}{p(x_i)p(c)} + \sum_c p(x_i) \log \frac{p(x_i,c)}{p(x_i)p(c)} - \sum_c (p(x_i)+p(x_j)) \log \frac {p(x_i,c)+p(x_i,c)}{(p(x_i)+p(x_j))p(c)} \]" src="form_14.png"/>
</p>
<p>Thus in a basic implementation of AIB, finding the optimal pair <img class="formulaInl" alt="$ij$" src="form_13.png"/> of feature values requires <img class="formulaInl" alt="$O(CN^2)$" src="form_17.png"/> operations in total. In order to join all the <img class="formulaInl" alt="$N$" src="form_18.png"/> values, we repeat this procedure <img class="formulaInl" alt="$O(N)$" src="form_5.png"/> times, yielding <img class="formulaInl" alt="$O(N^3 C)$" src="form_19.png"/> time and <img class="formulaInl" alt="$O(1)$" src="form_20.png"/> space complexity (this does not account for the space need to store the input).</p>
<p>The complexity can be improved by reusing computations. For instance, we can store the matrix <img class="formulaInl" alt="$D = [ D_{ij} ]$" src="form_21.png"/> (which requires <img class="formulaInl" alt="$O(N^2)$" src="form_3.png"/> space). Then, after joining <img class="formulaInl" alt="$ij$" src="form_13.png"/>, all of the matrix <em>D</em> except the rows and columns (the matrix is symmetric) of indexes <em>i</em> and <em>j</em> is unchanged. These two rows and columns are deleted and a new row and column, whose computation requires <img class="formulaInl" alt="$O(NC)$" src="form_22.png"/> operations, are added for the merged value <img class="formulaInl" alt="$x_{ij}$" src="form_23.png"/>. Finding the minimal element of the matrix still requires <img class="formulaInl" alt="$O(N^2)$" src="form_3.png"/> operations, so the complexity of this algorithm is <img class="formulaInl" alt="$O(N^2C + N^3)$" src="form_24.png"/> time and <img class="formulaInl" alt="$O(N^2)$" src="form_3.png"/> space.</p>
<p>We can obtain a much better expected complexity as follows. First, instead of storing the whole matrix <em>D</em>, we store the smallest element (index and value) of each row as <img class="formulaInl" alt="$(q_i, D_i)$" src="form_25.png"/> (notice that this is also the best element of each column since <em>D</em> is symmetric). This requires <img class="formulaInl" alt="$O(N)$" src="form_5.png"/> space and finding the minimal element of the matrix requires <img class="formulaInl" alt="$O(N)$" src="form_5.png"/> operations. After joining <img class="formulaInl" alt="$ij$" src="form_13.png"/>, we have to efficiently update this representation. This is done as follows:</p>
<ul>
<li>The entries <img class="formulaInl" alt="$(q_i,D_i)$" src="form_26.png"/> and <img class="formulaInl" alt="$(q_j,D_j)$" src="form_27.png"/> are deleted.</li>
<li>A new entry <img class="formulaInl" alt="$(q_{ij},D_{ij})$" src="form_28.png"/> for the joint value <img class="formulaInl" alt="$x_{ij}$" src="form_23.png"/> is added. This requires <img class="formulaInl" alt="$O(CN)$" src="form_29.png"/> operations.</li>
<li>We test which other entries <img class="formulaInl" alt="$(q_{k},D_{k})$" src="form_30.png"/> need to be updated. Recall that <img class="formulaInl" alt="$(q_{k},D_{k})$" src="form_30.png"/> means that, before the merge, the value closest to <img class="formulaInl" alt="$x_k$" src="form_31.png"/> was <img class="formulaInl" alt="$x_{q_k}$" src="form_32.png"/> at a distance <img class="formulaInl" alt="$D_k$" src="form_33.png"/>. Then<ul>
<li>If <img class="formulaInl" alt="$q_k \not = i$" src="form_34.png"/>, <img class="formulaInl" alt="$q_k \not = j$" src="form_35.png"/> and <img class="formulaInl" alt="$D_{k,ij} \geq D_k$" src="form_36.png"/>, then <img class="formulaInl" alt="$q_k$" src="form_37.png"/> is still the closest element and we do not do anything.</li>
<li>If <img class="formulaInl" alt="$q_k \not = i$" src="form_34.png"/>, <img class="formulaInl" alt="$q_k \not = j$" src="form_35.png"/> and <img class="formulaInl" alt="$D_{k,ij} < D_k$" src="form_38.png"/>, then the closest element is <img class="formulaInl" alt="$ij$" src="form_13.png"/> and we update the entry in constant time.</li>
<li>If <img class="formulaInl" alt="$q_k = i$" src="form_39.png"/> or <img class="formulaInl" alt="$q_k = j$" src="form_40.png"/>, then we need to re-compute the closest element in <img class="formulaInl" alt="$O(CN)$" src="form_29.png"/> operations.</li>
</ul>
</li>
</ul>
<p>This algorithm requires only <img class="formulaInl" alt="$O(N)$" src="form_5.png"/> space and <img class="formulaInl" alt="$O(\gamma(N) C N^2)$" src="form_41.png"/> time, where <img class="formulaInl" alt="$\gamma(N)$" src="form_42.png"/> is the expected number of times we fall in the last case. In common cases one has <img class="formulaInl" alt="$\gamma(N) \approx \mathrm{const.}$" src="form_43.png"/>, so the time saving is significant. </p>
</div></div>
     <!-- Doc Here -->
    </div>
   
   </div>
   <div class="clear">&nbsp;</div>
  </div> <!-- pagebody -->
  <div id="footer">
   &copy; 2007-12 Andrea Vedaldi and Brian Fulkerson
  </div> <!-- footer -->

  <!-- Google Analytics Begins -->
  <script xml:space="preserve" type="text/javascript">
   //<![CDATA[
    var localre = /vlfeat.org/;
    if(document.location.host.search(localre) != -1)
    {
   var gaJsHost = (("https:" == document.location.protocol) ? "https://ssl." : "http://www.");
   document.write(unescape("%3Cscript src='" + gaJsHost + "google-analytics.com/ga.js' type='text/javascript'%3E%3C/script%3E"));
   }
   //]]>
  </script>
  <script xml:space="preserve" type="text/javascript">
    //<![CDATA[
    var localre = /vlfeat.org/;
    if(document.location.host.search(localre) != -1)
    {

   try {
   var pageTracker = _gat._getTracker("UA-4936091-2");
   pageTracker._trackPageview();
   } catch(err) {}

   }
   //]]>
  </script>
  <!-- Google Analytics Ends -->
 </body>
</html>

 
